package mao.algorithm.sort;

/**
 * @author Totoro
 * @date 2020/7/10
 * @explain:
 */
public class FastSort {
    private static void fastSort(int [] data){
        fastSort(data,0,data.length ) ;
    }

    //交替查找。
    private static void fastSort(int [] data,int start,int end) {
        if(start+1 >= end) return;
        int temp = data[start];
        int tempStart=start;
        int tempEnd = end-1;

        /**
         * 正常情况是  start==end，正确退出
         * 开头就是最最大的： 最后一个挪到最前面，start++，一直到达和和end相等，
         *                  然后在最后一个放置最大值。
         * 开头就是最下值：end--直到等于start，
         */
        while(tempStart < tempEnd){
            while(tempStart < tempEnd && data[tempEnd]>temp ) //对于和需要比较的值相同的也需要交换，防止出现全是有序的或者开头就是最小的。
                tempEnd--;
            data[tempStart]= data[tempEnd];

            while(tempStart < tempEnd && data[tempStart]<temp )
                tempStart++;
            data[tempEnd]= data[tempStart];
        }
        //结束条件是end和start相同。
        data[tempEnd]=temp;

        fastSort(data,start,tempStart);
        fastSort(data,tempStart+1,end);//start加一越界。
    }

    public  static void main(String[] args) {
        int [] data = {1,2,3};
        fastSort(data);
        for(int i =0;i<data.length;i++){
            System.out.println(data[i]);
        }

    }

}

